package com.leetcode.array_matrix;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/9/8 20:16
 */
public class FindUnsortedSubarray_581 {

    public int findUnsortedSubarray(int[] nums) {
        //特判
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        //从右到左找下界，从左到右找上界
        int left = n - 2, right = 1;
        int curMin = nums[n - 1], curMax = nums[0];
        int up = 0, down = 1;

        //升序时移动 curMin 和 curMax
        //逆序时移动 down 和 up
        //不论顺序如何，双指针 left 和 right 一直保持移动
        while (left >= 0 && right < n) {

            if (nums[left] > curMin) {
                down = left;
            } else {
                curMin = nums[left];
            }
            left--;

            if (nums[right] < curMax) {
                up = right;
            } else {
                curMax = nums[right];
            }
            right++;
        }

        return up - down + 1;
    }

    public int findUnsortedSubarray2(int[] nums) {
        int[] copy = Arrays.copyOf(nums, nums.length);

        Arrays.sort(copy);
        int i = 0, j = nums.length - 1;
        while (i < j) {
            if (nums[i] != copy[i] && nums[j] != copy[j]) {
                break;
            }
            if (nums[i] == copy[i])
                i++;
            if (nums[j] == copy[j])
                j--;
        }

        return i >= j ? 0 : j - i + 1;
    }

    public static void main(String[] args) {
        FindUnsortedSubarray_581 ans = new FindUnsortedSubarray_581();

        int[] nums = {1, 2, 4, 5, 3};

        int res = ans.findUnsortedSubarray2(nums);
        System.out.println(res);

    }

}
